home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Tool Chest / QuickDraw GX / QuickDraw GX Info / QuickDraw GX Interfaces / Interfaces & Libraries / graphics libraries / cubic library.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-30  |  8.7 KB  |  313 lines  |  [TEXT/MPS ]
  1. /* graphics libraries:  
  2.   cubic library
  3.   by Hugo Ayala
  4.   Copyright 1991, 1992 Apple Computer, Inc.  All rights reserved. */
  5.  
  6. #include "graphics libraries.h"
  7.  
  8. typedef struct  {       /* this structure contains the cached cubic coefficients */
  9.   Fixed   ax, ay;
  10.   Fixed   bx, by;
  11.   Fixed   cx, cy;
  12.   Fixed   dx, dy;
  13. } xCubic;
  14.  
  15. typedef struct  {       /* this structure is just for a gxPath */
  16.   long    contours;
  17.   long    count;
  18.   long    flags;
  19.   gxPoint   data[ 32 ];
  20. } smallPath;
  21.  
  22.  
  23. /* macros to calculate the inner products */
  24.     
  25. #define XCube(xc,u) (FractMultiply(FractMultiply(FractMultiply((xc)->ax,(u))+(xc)->bx,(u))+(xc)->cx,(u))+(xc)->dx)
  26. #define YCube(xc,u) (FractMultiply(FractMultiply(FractMultiply((xc)->ay,(u))+(xc)->by,(u))+(xc)->cy,(u))+(xc)->dy)
  27.  
  28. #define XCubePrime(xc,u) (FractMultiply(FractMultiply((3*(xc)->ax),(u))+(2*(xc)->bx),(u))+(xc)->cx)
  29. #define YCubePrime(xc,u) (FractMultiply(FractMultiply((3*(xc)->ay),(u))+(2*(xc)->by),(u))+(xc)->cy)
  30.  
  31.  
  32. /* This routine calculates the number of cubics that would be needed to draw a with no more than a pixel error. */
  33. static long xCountQuadratics( const cubic *cube )
  34. {
  35.   Fixed ax = -cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x; /* first get the a vector components */
  36.   Fixed ay = -cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y;
  37.   short temp;
  38.   long count;
  39.   
  40.   if( ax < 0 )  /* make sure that they are positive */
  41.     ax = -ax;
  42.   if( ay < 0 )
  43.     ay = -ay;
  44.   ax = ( ay < ax ) ? ax : ay; /* pick the max one */
  45.   
  46.    temp = ( FixedDivide( ax, ff( 20 ) ) + 0xFFFF ) >> 16; /* we now divide by twenty and take the ceiling */
  47.  
  48.   /*    NOTE: if you want the tolerance to be .5 then   */
  49.   /*    divide ax by 10, .25 -> 5, etc        */
  50.   
  51.   /* this is a crude but fast and effective way of taking the cube root of    */
  52.   /* 'temp' which is between 0 and 27000                                      */
  53.   
  54.   if( temp <= 4096 ) {
  55.     if( temp <= 512 ) {
  56.       if( temp <= 64 ) {
  57.         if( temp <= 8 ) {
  58.           if( temp <= 1 )
  59.             count = 1;
  60.           else
  61.             count = 2;
  62.         } else {
  63.           if( temp <= 27 )
  64.             count = 3;
  65.           else
  66.             count = 4;
  67.         }
  68.       } else {
  69.         if( temp <= 216 ) {
  70.           if( temp <= 125 )
  71.             count = 5;
  72.           else
  73.             count = 6;
  74.         } else {
  75.           if( temp <= 343 )
  76.             count = 7;
  77.           else
  78.             count = 8;
  79.         }
  80.       }
  81.     } else {
  82.       if( temp <= 1728 ) {
  83.         if( temp <= 1000 ) {
  84.           if( temp <= 729 )
  85.             count = 9;
  86.           else
  87.             count = 10;
  88.         } else {
  89.           if( temp <= 1331 )
  90.             count = 11;
  91.           else
  92.             count = 12;
  93.         }
  94.       } else {
  95.         if( temp <= 2744 ) {
  96.           if( temp <= 2197 )
  97.             count = 13;
  98.           else
  99.             count = 14;
  100.         } else {
  101.           if( temp <= 3375 )
  102.             count = 15;
  103.           else
  104.             count = 16;
  105.         }
  106.       }
  107.     }
  108.   } else {
  109.     if( temp <= 13824 ) {
  110.       if( temp <= 8000 ) {
  111.         if( temp <= 5832 ) {
  112.           if( temp <= 4913 )
  113.             count = 17;
  114.           else
  115.             count = 18;
  116.         } else {
  117.           if( temp <= 6859 )
  118.             count = 19;
  119.           else
  120.             count = 20;
  121.         }
  122.       } else {
  123.         if( temp <= 10648 ) {
  124.           if( temp <= 9261 )
  125.             count = 21;
  126.           else
  127.             count = 22;
  128.         } else {
  129.           if( temp <= 12167 )
  130.             count = 23;
  131.           else
  132.             count = 24;
  133.         }
  134.       }
  135.     } else {
  136.       if( temp <= 21952 ) {
  137.         if( temp <= 17576 ) {
  138.           if( temp <= 15625 )
  139.             count = 25;
  140.           else
  141.             count = 26;
  142.         } else {
  143.           if( temp <= 19683 )
  144.             count = 27;
  145.           else
  146.             count = 28;
  147.         }
  148.       } else {
  149.         if( temp <= 27000 ) {
  150.           if( temp <= 24389 )
  151.             count = 29;
  152.           else
  153.             count = 30;
  154.         } else  /* because our gxPath can only contain 32 -2 points we stop here */
  155.           count = 30;
  156.       }
  157.     }
  158.   }
  159.   return  count;
  160. }
  161.  
  162.  
  163. /* This routine is where the cuadratic points get computed.  Note that this
  164.   routine never fills in the last gxPoint in the code. It also assumes that the first gxPoint has been moved in by the caller.
  165.     
  166.   cubic     ->      a pointer to the cubic
  167.   count   ->      the number of points other than the two end ones that we need to generate
  168.   storage   ->      a place to put the points that are generated
  169. */
  170. static gxPoint *ComputePoints( const cubic *cube, long count,  gxPoint *storage )
  171. {
  172.   Fixed  *ptr = &storage->x;
  173.   
  174.   if( 0 < count )
  175.   { xCubic x;
  176.     fract  n  = FractDivide( 1, count );      /*    LongInt / LongInt -> frac   */
  177.     fract u = n;
  178.     Fixed tempx1 = cube->a.x >> 1;  
  179.     Fixed tempy1 = cube->a.y >> 1;
  180.     Fixed tempx2, tempy2;
  181.     
  182.     /* we compute the coefficients for this cubic -- for efficient computation later  */
  183.     
  184.     x.ax = -cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x;
  185.     x.ay = -cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y;
  186.     x.bx = 3 * cube->a.x - 6 * cube->b.x + 3 * cube->c.x;
  187.     x.by = 3 * cube->a.y - 6 * cube->b.y + 3 * cube->c.y;
  188.     x.cx = -3 * cube->a.x + 3 * cube->b.x;
  189.     x.cy = -3 * cube->a.y + 3 * cube->b.y;
  190.     x.dx = cube->a.x;
  191.     x.dy = cube->a.y;
  192.     tempx2 = FractMultiply( x.cx, n ) >> 2;
  193.     tempy2 = FractMultiply( x.cy, n ) >> 2;
  194.     
  195.     for( ; 0 < count; --count )  
  196.     { Fixed ntempx1 = XCube( &x, u ) >> 1;  /* compute the next gxPoint sequence */
  197.       Fixed ntempy1 = YCube( &x, u ) >> 1;
  198.       Fixed  ntempx2 = FractMultiply( XCubePrime( &x, u ), n ) >> 2;
  199.       Fixed ntempy2 = FractMultiply( YCubePrime( &x, u ), n ) >> 2;
  200.         
  201.       *ptr++ = tempx1 + tempx2 + ntempx1 - ntempx2; /* store the gxPoint */
  202.       *ptr++ = tempy1 + tempy2 + ntempy1 - ntempy2;
  203.       tempx1 = ntempx1;
  204.       tempx2 = ntempx2;
  205.       tempy1 = ntempy1;
  206.       tempy2 = ntempy2;
  207.       u += n;
  208.     }
  209.     *ptr++ = cube->d.x;  /* move in the last gxPoint of the cubic */
  210.     *ptr++ = cube->d.y;
  211.   }
  212.   return (gxPoint *) ptr;
  213. }
  214.  
  215.  
  216. /* This routine fills in a data structure for a gxPath with the information of a cubic.
  217.   pathptr   ->    a pointer to the gxPath
  218.   cube      ->    the cubic
  219.   count   ->    how many points to use
  220. */
  221. static void CubicPath( smallPath *pathptr, const cubic *cube, const long count )
  222. {
  223.   gxPoint  *ptr;
  224.  
  225.   pathptr->contours = 1;
  226.   pathptr->count = count + 2;
  227.   pathptr->flags = ~((unsigned long) 0x80000000 >> count + 1) & 0x7FFFFFFF;
  228.   
  229.   ptr = pathptr->data;
  230.   *ptr++ = cube->a;
  231.   ComputePoints( cube, count, ptr );
  232. }
  233.  
  234.  
  235. /* This routine draws a cubic with the given fill */
  236. void DrawCubic( const cubic *cube, gxShapeFill theFill )
  237. {
  238.   gxShape sh = NewCubic( cube );
  239.   
  240.   if (theFill != GXGetShapeFill(sh))
  241.     GXSetShapeFill(sh, theFill);
  242.   GXDrawShape( sh );
  243.   GXDisposeShape( sh );
  244. }
  245.  
  246.  
  247. /* This routine sets the points inside of a gxPath to be those of the given cubic */
  248. void SetCubic( gxShape dest, const cubic *cube )
  249. {
  250.   smallPath   pathrec;
  251.  
  252.   CubicPath( &pathrec, cube, xCountQuadratics( cube ) );
  253.   GXSetPaths( dest, (gxPaths *) &pathrec );
  254. }
  255.  
  256.  
  257. /* This routine makes a new cubic that has a tolerance of one pixel. */
  258. gxShape NewCubic( const cubic *cube )
  259. { 
  260.   smallPath   pathrec;
  261.  
  262.   CubicPath( &pathrec, cube, xCountQuadratics( cube ) );
  263.   return GXNewPaths((gxPaths *) &pathrec );
  264. }
  265.  
  266.  
  267. /* This routine is the same as above except that it has an optional parameter for determining how many points to
  268.    include in a gxPath.  The number determines the number of points 'off' the gxCurve which are needed.
  269.  
  270.   If you use this routine you should link it in with another which determines the number of points to be used.
  271.   Here is an example that depends on a global variable 'gerror' of type extended.  Also, see the 'optimized'
  272.   example for 'xCountQuadratics' above.
  273. */  
  274. #ifdef NewCubic2Defined
  275.   #include <math.h>
  276.   
  277.   #ifdef THINK_C
  278.     #define extended long double
  279.     #define power pow
  280.   #endif
  281.   
  282.   #define FixedToExtended(a) ((extended)(a) / fixed1)
  283.   
  284.   extended gerror = 1.0;
  285.   
  286.   static long CountQuadratics( const cubic *cube )
  287.   {
  288.     extended ax = FixedToExtended( - cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x );
  289.     extended ay = FixedToExtended( - cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y );
  290.     extended a = sqrt( ax * ax + ay * ay );
  291.     extended n = power( ( a / ( 20.0 * gerror ) ), 1.0 / 3.0 );
  292.     long count = ceil( n );
  293.   
  294.     if( count <= 0 ) 
  295.       count += 1;
  296.     return count;
  297.   }
  298.   
  299.   gxShape NewCubic2( const cubic *cube, const long count );
  300.   gxShape NewCubic2( const cubic *cube, const long count )
  301.   { 
  302.     smallPath   pathrec;
  303.   
  304.     CubicPath( &pathrec, cube, ( count <= 0 ) ? CountQuadratics( cube ) : count );
  305.     return  GXNewPaths((gxPaths *) &pathrec );
  306.   }
  307.   #ifdef THINK_C
  308.     #undef extended
  309.   #endif
  310.   
  311.   #undef FixedToExtended
  312. #endif
  313.